DEEP-FRING (DEEP-FRI over Rings)

Goal. Generalize FRI, Schwartz-Zippel and FFT to a commutative ring of the form $R = \mathbb Z/m \mathbb Z$ where $m = 2^b ⋅ k$ or something similar.

We want this to be able to construct a $2^{64}$ sub-ring that captures the behaviour of binary numbers without much fuzz.

We can tweak $k$ to guarantee the existence of roots of unity of order $2^r$, which will power FRI and FFT.

The ring $R$ is

Consequently, the ring of polynomials over it, $R[X]$ is

Note. We need an integral domain in order to have the common rules on degree of the polynomial: https://en.wikipedia.org/wiki/Degree_of_a_polynomial#Behavior_under_polynomial_operations

To do. It does seem that this only reduces the degrees of the polynomials, and potentially only with neglible probability. So much of the theory can be salvaged. (i.e. $\deg (PQ) \leq (\deg P)(\deg Q)$).


Roots of unity


Schwartz-Zippel

https://mathoverflow.net/questions/186074/can-schwartz-zippel-be-formulated-for-commutative-rings-instead-of-fields


Unique factorization

For some theorems we need Polynomials to have a unique factorization into irreducible factors (i.e. in Plonk's multi-set check). This requires the field to be a unique factorization domain, but it isn't. In fact, it is not even an integral ring.

https://en.wikipedia.org/wiki/Unique_factorization_domain

https://en.wikipedia.org/wiki/Polynomial_ring#Factorization_in_K[X]


FFT+FRI

https://users.cs.duke.edu/~reif/courses/alglectures/reif.lectures/ALG3.2.pdf

FFT Seems to not be an issue as long as the roots of unity exist. FRI will follow the same path.


Reed-solomon over Rings

https://hal.inria.fr/hal-00670004v2/document


Commutative rings

A commutative ring is a set $\mathbb R$ with two binary operations $+$ and $⋅$ and two elements $0, 1 \in \mathbb R$ s.t.:

Q: Additive inverses unique? Q: Multiplicative inverses unique?

Definition. (Additive inverse). $-a$. By the axioms these always exist.

Definition. (Multiplicative inverse). $a^{-1}$. These do not necessarily exist.

Definition. (Unit). If $a$ has an inverse, it is called a unit.

Definition. (Zero divisor). If $a$ has an element $b$ such that $ab = 0$, it is called a zero divisor.

Definition. (Nilpotent). If $a$ has a positive number $n$ such that $a^n = 0$, it is called nilpotent.

Lemma. If $a$ is nilpotent then $1-a$ is a unit.

https://en.wikipedia.org/wiki/Root_of_unity_modulo_n

https://en.wikipedia.org/wiki/Root_of_unity_modulo_n#Finding_an_n_with_a_primitive_k-th_root_of_unity_modulo_n

Remco Bloemen
Math & Engineering
https://2π.com